/**
 * @Author：JIAMIN_TANG
 * @Description:ArrayList常用方法的简单实现
 * @CreateTime：2025/10/9 21:46
 */
public class MyArrayList {
    //真正存储数据，顺序表本身就是基于数组的封装
    private int[] arr;
    //约定arr中的前size个元素，表示有效元素
    //注意区分有效长度size、数组长度length、容量capacity三者的区别
    private int size = 0;//初始化数组有效容量为0

    //无参构造函数
    public MyArrayList(){
        arr = new int[10];//默认容量为10
    }

    //有参构造方法
    public MyArrayList(int capacity){
        arr = new int[capacity];//初始化数组，但是此时数组里面还是空的，没有内容的，只是分配了空间，此时数组有效长度size是0，等往数组中添加了元素之后size的值才会变成非零的
    }

    //获取有效元素个数
    public int size(){
        return size;
    }

    //新增元素，尾插
    public void add(int val){
        //把新的元素放到最后一个位置上，下标为size的元素
        //注意这里的size指的是数组的有效长度，数组没有插入新的元素之前它的元素的索引范围是[0,size-1],在这个范围的后面再插入一个元素（即尾插）就是在索引为size的位置插入一个元素，插入完毕之后再将size+1——更新数组有效长度即可
        //数组如果满了，则需要扩容
        if(size == arr.length){
            resize();
        }
        arr[size] = val;
        size++;
    }

    //在任意位置插入元素
    public void add(int index,int val){
        if(index < 0 || index > size){//注意这里index == size是允许的，因为在有效长度size的位置插入一个元素就是尾插，但是index > size就是不允许的，因为最大的插入元素的范围是尾插的那个索引的位置——即size(相当于在原来数组的基础上直接加一个元素在数组屁股后面)，但是如果超过了size了的话，那么这个位置跟数组最后一个元素size-1的位置之间是有间隔的，这会出Bug,不可以这样插
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        //如果数组已经满了，继续添加元素，要先扩容
        if(size == arr.length){
            resize();
        }
        //先把要插入位置及其该位置往后的所有元素同意往后挪一个位置
        //如果元素本身下标是i，就把这个元素赋值到i+1的位置上
        //index位置的元素也需要往后挪一下，i>=index
        for(int i = size - 1;i >= index;i--){//这里是从最后一个位置的元素往后挪动，然后从后往前把要往后挪动的元素从后往前依次往后挪动，因为还没有插入新的元素之前，最后一个元素的下标索引是size-1,所以for循环中i的起始值是size-1
            arr[i+1] = arr[i];
        }
        //此时就相当于把index位置腾出来了，把新元素放到index位置上就好了
        arr[index] = val;
        //更新size
        size++;
    }

    //扩容函数
    private void resize(){
        //创建一个更长的数组，将其容量设置为原来数组容量的1.5倍
        // int[] newArr = new int[(int)(arr.length*1.5)];
        //使用位运算符会更快，在CPU中，位运算比乘法运算更快，尤其在大规模数据操作时，性能差异更明显；日常的工作中使用位运算符写得也更多，但是这种小的运算速率也提升不了很明显，反正位运算符是常用的就是了
        int[] newArr = new int[arr.length+(arr.length>>1)];
        //把原来的旧数组复制到新数组上
        for(int i = 0;i < size;i++){
            newArr[i] = arr[i];
        }
        //用新的数组代替旧数组
        //此时旧的数组就会被垃圾回收给释放掉
        arr = newArr;
    }

    /*关于set和get方法的知识点扩展：
     顺序表是可以随机访问的，CPU可以立即计算出数组中某个元素所在的位置的索引，然后直接移动到这个元素的索引的位置(也可以理解是瞬间移动到那里)，移动的速度很快，
     可以认为CPU访问数组中的每一个元素的时间都是一样的，时间很短，所以时间复杂度为O(1)，
     但是硬盘访问的话，硬盘做不到随机访问，硬盘更擅长做的事是顺序读写，即顺序访问，要一个个遍历，速度很慢，时间复杂度是O(N)，
     但一般来说是不会直接操作硬盘的，都是先把数据从硬盘读到内存中，然后再操作内存中的数据，所以一般来说访问数组中的元素的时间复杂度都是O(1)
    顺序表最大的特点就是可以随机访问元素，时间复杂度是O(1)，因为顺序表是基于数组实现的，而数组是支持随机访问的*/

    //获取指定位置（下标）的元素值
    public int get(int index){
        //记得考虑数组越界的问题
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("下标越界："+index);
        }
        return arr[index];
    }

    //修改指定下标的元素值
    public void set(int index,int val){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("下标越界："+index);
        }
        arr[index] = val;
    }

    //根据下标删除元素并返回要删除的元素的值
    //先找到要删除的元素，然后把要删除的元素后面的元素全部都往前挪一个位置，直接把原来的要删除的元素覆盖掉就好了，然后更新size的值即可
    public int remove(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("下标越界："+index);
            }
        int result = arr[index];
        if(index == size-1){//尾删，直接更新size的值即可，然后JVM会自动把最后一个元素给垃圾回收掉
            size--;
            return result;
        }//这里尾删是属于特殊情况，在刚开始写代码的时候需要单独处理，写完代码之后优化的时候可以看一下怎么让代码更加简介好看，然后此处我们会发现，这段代码在下面的普通情况中其实是已经包括了的，所以其实可以把这段代码删掉，不删也可，因为不影响程序的正确性，只是会比较冗余
        for(int i = index;i< size-1;i++){
            arr[i] = arr[i+1];
        }
        size--;
        return result;
    }

    //按值删除元素
    public void delete(int val){
        //1.先找到这个值所在的位置
//        int index = 0;
//        for(;index < size;index++){//最后一次循环，即i=size-1的时候，进入循环时，i也进行了一次++操作，所以i最终会等于size
//            if(arr[index]==val){
//                //找到了
//                break;
//            }
//        }
//        if(index==size){//如果循环没有找到的话，没有执行brek，那么i的最终值是size，就是说在数组的最后一个有数值的位置size-1处也没有找到这个元素，所以此时说明没有找到这个元素，不用删除
//            System.out.println("没有你要删除的元素"+val);
//            return;
//        }
        //也可以直接调用indexOf方法来查找元素所在的位置
        int index = indexOf(val);
        //2.找到了，删除这个元素，直接调用上面的remove方法删除即可，方便，不用重复写删除逻辑，遇到需要修改的时候直接改remove这个方法里的代码即可，方便
        //index就是要删除的元素的下标
//        for(int i = index;i < size-1;i++){
//            arr[i] = arr[i+1];
//        }
//        size--;
        remove(index);
    }


    //打印操作，搞一个toString方法，把MyArrayList转化为字符串
    /*因为System.out.println(list)是调用的ArrayList类型里的toString方法进行打印的，
    所以如果要单独实现ArrayList方法里的打印功能的话，就要自己实现ArrayList里的toString方法*/
    @Override
    public String toString(){
    //打印格式形如：[1,2,3]
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for(int i = 0;i < size;i++){
            stringBuilder.append(arr[i]);
            if(i < size - 1){
                //最后一个元素，后面不需要添加逗号
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();//这里的toString()是StringBuilder类本身自带的方法，StringBuilder内部自己重写了这个打印的方法，用来打印stringBuilder这个StringBuilder类型的对象
    }

    //判断元素是否存在
    public boolean contains(int val){
        for(int i = 0;i < size;i++){
            if(arr[i] == val){
                return true;
            }
        }
        return false;
    }

    //查找元素所在位置，返回元素所在位置的下标
    public int indexOf(int val){
        for(int i = 0;i < size;i++){
            if(arr[i] == val){
                return i;
            }
        }
        System.out.println("没有找到你要查找的元素"+val);
        return -1;
    }

    //从顺序表尾部开始查找元素，返回从后往前出现第一次的该元素所在位置的下标
    public int lastIndexOf(int val){
        for(int i = size - 1;i >= 0;i--){
            if(arr[i] == val){
                return i;
            }
        }
        return -1;
    }

    //清空数组元素，但是不释放内存，盒子还在，只是盒子内部的东西没有了
    public void clear(){
        size = 0;
        //直接把数组的有效容量设置为0即可，但是不用把数组的每个元素都赋值为0，因为JVM会自动把这些没有用的元素给垃圾回收掉
    }


    //add尾插法和toString打印方法的测试单元
    private static void test1(){
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        System.out.println(list.size());
        System.out.println(list);
    }

    //add(index,val)方法的测试单元
    private static void test2(){
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(0,100);
        System.out.println(list);
        list.add(1,200);
        System.out.println(list);
        list.add(6,300);
        System.out.println(list);
    }

    //remove方法的测试单元
    private static void test3(){
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);

        list.remove(0);
        System.out.println(list);
        list.remove(2);
        System.out.println(list);
        list.remove(4);
        System.out.println(list);
        list.remove(10);
        System.out.println(list);

    }

    //delete方法的测试单元
    private static void test4(){
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);

        list.delete(3);
        System.out.println(list);
        list.delete(5);
        System.out.println(list);
        list.delete(100);
        System.out.println(list);

    }

    //contains、indexOf方法的单元
    private static void test5(){
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);

//        System.out.println(list.contains(2));
//        System.out.println(list.contains(100));
//
//        System.out.println(list.indexOf(5));
//        System.out.println(list.indexOf(100));

        //测试方法的优化
        //对于单元测试来说，直接打印通过肉眼分析判断是很容易出错的，所以我们可以把预期结果和实际结果进行对比，如果一致就说明测试通过，否则测试不通过
        //测试contains方法
        if(list.contains(3)){
            System.out.println("测试通过");
        }else{
            System.out.println("测试不通过");
        }

        if(!list.contains(100)){
            System.out.println("测试通过");
        }else{
            System.out.println("测试不通过");
        }

        //测试indexOf方法
        if(list.indexOf(5)==4){
            System.out.println("测试通过");
        }else{
            System.out.println("测试不通过");
        }

        if(list.indexOf(100)==-1){
            System.out.println("测试通过");
        }else{
            System.out.println("测试不通过");
        }

        //测试lastIndexOf方法
        if(list.lastIndexOf(5)==4){
            System.out.println("测试通过");
        }else{
            System.out.println("测试不通过");
        }

        if(list.lastIndexOf(100) == -1){
            System.out.println("测试通过");
        }else{
            System.out.println("测试不通过");
        }

    }


    public static void main(String[] args){
//        test1();//调用add和toString方法的测试单元
//        test2();//调用add(index,val)方法的测试单元
//        test3();//调用remove()方法的测试单元
//        test4();//调用delete()方法的测试单元
        test5();//调用contains()方法的测试单元
    }
}
